//题目:
// 给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数  。

// 你可以对一个单词进行如下三种操作：
// 插入一个字符
// 删除一个字符
// 替换一个字符
 
// 示例 1：
// 输入：word1 = "horse", word2 = "ros"
// 输出：3
// 解释：
// horse -> rorse (将 'h' 替换为 'r')
// rorse -> rose (删除 'r')
// rose -> ros (删除 'e')

// 示例 2：
// 输入：word1 = "intention", word2 = "execution"
// 输出：5
// 解释：
// intention -> inention (删除 't')
// inention -> enention (将 'i' 替换为 'e')
// enention -> exention (将 'n' 替换为 'x')
// exention -> exection (将 'n' 替换为 'c')
// exection -> execution (插入 'u')
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
//代码
class Solution 
{
public:
    int minDistance(string word1, string word2) 
    {
        //解题思路：①找到word1和word2中最长相同子序列； ②计算结果  运行结果：× 行不通

        // int m=word1.size(),n=word2.size();
        // word1=" "+word1,word2=" "+word2;
        
        // //1.创建dp表————dp[i][j]表示：word1中[0,i]子串转换成word2中[0,j]子串，所需的最小操作步骤
        // vector<vector<pair<int,string>>> dp(m+1,vector<pair<int,string>>(n+1));
        // //2.初始化 ———— 虚拟行、列
        // //3.填表 ———— 从上玩下 + 从左往右
        // for(int i=1;i<=m;i++)
        // {
        //     for(int j=1;j<=n;j++)
        //     {
        //         if(word1[i]==word2[j]) 
        //         {
        //             dp[i][j].first=dp[i-1][j-1].first+1;
        //             dp[i][j].second=dp[i-1][j-1].second+word1[i]; //公共子序列
        //         }
        //         else if(dp[i][j-1].first>dp[i-1][j].first)
        //         {
        //             dp[i][j].first=dp[i][j-1].first;
        //             dp[i][j].second=dp[i][j-1].second;
        //         }
        //         else
        //         {
        //             dp[i][j].first=dp[i-1][j].first;
        //             dp[i][j].second=dp[i-1][j].second;
        //         }
        //     }
        // }
        // string str=dp[m][n].second;
        // //此时，dp[m][n].second 就是word1和word2的最长公共子序列
        // //4.找出 str 分别在word1和word2中的位置
        // vector<int> arr1,arr2;
        // int pos_str=0,pos_f=1;
        // while(pos_str<str.size() && pos_f<=m)
        // {
        //     if(str[pos_str]==word1[pos_f])
        //         arr1.push_back(pos_f),pos_str++;
        //     pos_f++;
        // }
        // pos_str=0,pos_f=0;
        // while(pos_str<str.size() && pos_f<=n)
        // {
        //     if(str[pos_str]==word2[pos_f])
        //         arr2.push_back(pos_f),pos_str++;
        //     pos_f++;
        // }
        // for(auto x:arr1) cout<<x<<" ";
        // cout<<endl;
        // for(auto x:arr2) cout<<x<<" ";

        //动态规划
        int m=word1.size(),n=word2.size();
        word1=" "+word1,word2=" "+word2;

        //1.创建dp表————dp[i][j]表示:s1中[0,i]区间和s2中[0,j]区间，所有子序列中，最长公共子序列的长度
        vector<vector<int>> dp(m+1,vector<int>(n+1));
        //2.初始化
        for(int i=1;i<=m;i++) dp[i][0]=i;
        for(int j=1;j<=n;j++) dp[0][j]=j;
        //3.填表 ———— 从上玩下 + 从左往右
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(word1[i]==word2[j]) 
                    dp[i][j]=dp[i-1][j-1];
                else
                    dp[i][j]=1+min({dp[i-1][j-1],dp[i][j-1],dp[i-1][j]});
            }
        }
        //4.确定返回值
        return dp[m][n];
    }
};